package sortAlgorithm;

import java.util.Arrays;

public class CountSort {
	public static void main(String[] args) {
//		int[] a = {5, 3, 6, 2, 99,9,28};
		int[] a = {-3,-24,-2,4,-3};
//		int[] a = { -3, -24, -2, -4, -3 };
		countSortUp(a);
		System.out.println(Arrays.toString(a));
	}

	/**
	 * 计数排序 时间复杂度：N+N+K(原始数组中最大值) 空间复杂度：原数组中最大元素值（负数取绝对值） 非原址排序
	 * 稳定性：相同元素不会出现交叉，非原址都是拷来拷去 如果要优化，辅助数组长度为max-min+1，可以缩短一点数组长度
	 * 计数有缺陷，数组较为稠密，范围较小时适用
	 *
	 * @param source 要排序的数组
	 */
	public static void countSortUp(int[] source) {
		int maxPositive = source[0], minNegative = source[0];
		int flagNegative = 0; // 为1，则有负数
		int flagPositive = 0; // 为1，则有正数
		for (int i : source // 求数组元素绝对最大值
		) {
			if (i < 0) {
				flagNegative = 1;
				if (i < minNegative) {
					minNegative = i;
				}
			} else {
				flagPositive = 1;
				if (i > maxPositive) {
					maxPositive = i;
				}
			}
		}
		int current = 0; // 指针，用于将辅助数组的数填到原始数组
		if (flagNegative != 1) { // 数组元素只存在存在正数
			int[] positiveHelper = new int[maxPositive + 1];
			for (int i : source // 将原数组值作为辅助数组下标，将该位加1
			) {
				positiveHelper[i]++;
			}
			for (int i = 0; i < positiveHelper.length; i++) {
				while (positiveHelper[i] > 0) { // 将辅助数组元素非零下标，赋值给原数组
					source[current++] = i;
					positiveHelper[i]--;
				}
			}
		}
		if (flagPositive != 1) { // 数组元素只存在负数
			int[] negativeHelper = new int[Math.abs(minNegative) + 1];
			for (int i : source) {
				negativeHelper[Math.abs(i)]++; // 取绝对值做辅助数组下标
			}
			// 元素小的取绝对值，反而大，逆序读取
			for (int i = negativeHelper.length - 1; i >= 0; i--) {
				while (negativeHelper[i] > 0) {
					source[current++] = -i;
					negativeHelper[i]--;
				}
			}

		}
		// 前两种结合
		if ((flagPositive == 1) && (flagNegative == 1)) { // 数组元素有负有正
			int[] positiveHelper = new int[maxPositive + 1];
			int[] negativeHelper = new int[Math.abs(minNegative) + 1];
			for (int i : source) {
				if (i > 0) {
					positiveHelper[i]++;
				} else {
					negativeHelper[Math.abs(i)]++;
				}
			}
			for (int i = negativeHelper.length - 1; i >= 0; i--) {
				while (negativeHelper[i] > 0) {
					source[current++] = -i;
					negativeHelper[i]--;
				}
			}
			for (int i = 0; i < positiveHelper.length; i++) {
				while (positiveHelper[i] > 0) {
					source[current++] = i;
					positiveHelper[i]--;
				}
			}
		}
	}
	public static void countSortDown(int[] source) {
		int maxPositive = source[0], minNegative = source[0];
		int flagNegative = 0; // 为1，则有负数
		int flagPositive = 0; // 为1，则有正数
		for (int i : source // 求数组元素绝对最大值
		) {
			if (i < 0) {
				flagNegative = 1;
				if (i < minNegative) {
					minNegative = i;
				}
			} else {
				flagPositive = 1;
				if (i > maxPositive) {
					maxPositive = i;
				}
			}
		}
		int current = 0; // 指针，用于将辅助数组的数填到原始数组
		if (flagNegative != 1) { // 数组元素只存在存在正数
			int[] positiveHelper = new int[maxPositive + 1];
			for (int i : source // 将原数组值作为辅助数组下标，将该位加1
			) {
				positiveHelper[i]++;
			}
			for (int i = positiveHelper.length-1; i >=0 ; i--) {
				while (positiveHelper[i] > 0) { // 将辅助数组元素非零下标，赋值给原数组
					source[current++] = i;
					positiveHelper[i]--;
				}
			}
		}
		if (flagPositive != 1) { // 数组元素只存在负数
			int[] negativeHelper = new int[Math.abs(minNegative) + 1];
			for (int i : source) {
				negativeHelper[Math.abs(i)]++; // 取绝对值做辅助数组下标
			}
			// 元素大的取绝对值，反而小，正序读取
			for (int i =0; i <negativeHelper.length; i++) {
				while (negativeHelper[i] > 0) {
					source[current++] = -i;
					negativeHelper[i]--;
				}
			}

		}
		// 前两种结合
		if ((flagPositive == 1) && (flagNegative == 1)) { // 数组元素有负有正
			int[] positiveHelper = new int[maxPositive + 1];
			int[] negativeHelper = new int[Math.abs(minNegative) + 1];
			for (int i : source) {
				if (i > 0) {
					positiveHelper[i]++;
				} else {
					negativeHelper[Math.abs(i)]++;
				}
			}
			for (int i = positiveHelper.length-1; i >=0 ; i--) {
				while (positiveHelper[i] > 0) { // 将辅助数组元素非零下标，赋值给原数组
					source[current++] = i;
					positiveHelper[i]--;
				}
			}
			for (int i =0; i <negativeHelper.length; i++) {
				while (negativeHelper[i] > 0) {
					source[current++] = -i;
					negativeHelper[i]--;
				}
			}
		}
	}
}
